题解 CF366C 【Dima and Salad】

发表于 | 更新于

$Description$

有$n$个水果,每个水果有两个属性：美味值和卡路里值。现在选用若干个（至少$1$个）水果制作一份特殊的沙拉，沙拉的美味值为所选的水果的美味值的和，沙拉的卡路里值为所选水果的卡路里值的和。要保证沙拉的美味值恰好是卡路里值的$K$倍。请计算该沙拉美味值最大为多少。

$Solution$

根据题意可得$\sum a_{i}-k\times\sum b_{i}=0$

所以我们考虑将$a_{i}$作为价值，$a_{i}-k\times b_{i}$作为重量，进行背包转移即可，由于重量有可能是负数，所以应用$map$存储转移数组或是将下标强行加上一个大数。

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 30007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int a[N],v[N],f[200][N],g[200][N];
signed main(){
    int n=read(),k=read(),m=100*n;memset(f,-0x7f,sizeof(f));memset(g,-0x7f,sizeof(g));
    for (int i=1;i<=n;++i)a[i]=read();
    for (int i=1;i<=n;++i)v[i]=a[i]-read()*k;
    f[0][m]=0;
    for (int i=1;i<=n;++i)
        for (int j=0;j<=2*m;++j)
            f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+a[i]);
    cout<<(f[n][m]!=0?f[n][m]:-1)<<endl;
    return 0;
}